import math


def multiplicative_cipher_encrypt(plaintext, key):
    ciphertext = []
    # 确保密钥与26互质
    if math.gcd(key, 26) != 1:
        raise ValueError("密钥必须与26互质")

    for char in plaintext.upper():
        if char.isalpha():
            # 将字母转换为0-25的数字
            num = ord(char) - ord('A')
            # 加密公式：C = (P * key) mod 26
            encrypted_num = (num * key) % 26
            # 转换回大写字母
            ciphertext.append(chr(encrypted_num + ord('A')))
        else:
            # 非字母字符直接保留
            ciphertext.append(char)
    return ''.join(ciphertext)


def multiplicative_cipher_decrypt(ciphertext, key):
    plaintext = []
    # 计算模逆元
    try:
        # 使用扩展欧几里得算法计算逆元
        inv_key = pow(key, -1, 26)
    except ValueError:
        raise ValueError("无法解密：密钥与26不互质")

    for char in ciphertext.upper():
        if char.isalpha():
            num = ord(char) - ord('A')
            # 解密公式：P = (C * inv_key) mod 26
            decrypted_num = (num * inv_key) % 26
            plaintext.append(chr(decrypted_num + ord('A')))
        else:
            plaintext.append(char)
    return ''.join(plaintext)


# 使用示例
if __name__ == "__main__":
    key = 5  # 必须与26互质（如3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25）
    plaintext = "HELLOWORLD"

    encrypted = multiplicative_cipher_encrypt(plaintext, key)
    print(f"加密结果: {encrypted}")

    decrypted = multiplicative_cipher_decrypt(encrypted, key)
    print(f"解密结果: {decrypted}")